package com.yequan.leetcode.tree.treebfs;

import com.yequan.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author : Administrator
 * @date : 2020/5/2
 */
public class RecodeTreeBfs {

    class WithQueue {

        /**
         * 使用队列实现广度优先
         */
        public List<Integer> bfs1(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                ans.add(node.val);
                if (null != node.left) {
                    queue.offer(node.left);
                }
                if (null != node.right) {
                    queue.offer(node.right);
                }
            }
            return ans;
        }

        public List<Integer> bfs2(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                res.add(node.val);
                if (null != node.left) {
                    queue.offer(node.left);
                }
                if (null != node.right) {
                    queue.offer(node.right);
                }
            }
            return res;
        }

        public List<Integer> bfs3(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            if (null != root) {
                queue.offer(root);
            }
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                res.add(node.val);
                if (null != node.left) {
                    queue.offer(node.left);
                }
                if (null != node.right) {
                    queue.offer(node.right);
                }
            }
            return res;
        }

        public List<Integer> bfs4(TreeNode root) {
            if (null == root) {
                return null;
            }
            List<Integer> res = new ArrayList<>();
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                res.add(node.val);
                if (null != node.left) {
                    queue.offer(node.left);
                }
                if (null != node.right) {
                    queue.offer(node.right);
                }
            }
            return res;
        }

        public List<Integer> bfs5(TreeNode root) {
            if (null == root) {
                return null;
            }
            List<Integer> res = new ArrayList<>();
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                res.add(node.val);
                if (null != node.left) {
                    queue.offer(node.left);
                }
                if (null != node.right) {
                    queue.offer(node.right);
                }
            }
            return res;
        }

        public List<Integer> bfs6(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode currentNode = queue.poll();
                res.add(currentNode.val);
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            return res;
        }

        public List<Integer> bfs7(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode currentNode = queue.poll();
                res.add(currentNode.val);
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            return res;
        }

        public List<Integer> bfs8(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode currentNode = queue.poll();
                res.add(currentNode.val);
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            return res;
        }

        public List<Integer> bfs9(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                res.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            return res;
        }

    }

    class withRecursion {

        public void bfs1(TreeNode node, int level, List<List<Integer>> res) {
            if (node == null) {
                return;
            }
            if (level == res.size()) {
                res.add(new ArrayList<>());
            }
            res.get(level).add(node.val);
            if (node.left != null) {
                bfs1(node.left, level + 1, res);
            }
            if (node.right != null) {
                bfs1(node.right, level + 1, res);
            }
        }

        public void bfs2(TreeNode node, int level, List<List<Integer>> res) {
            if (node == null) {
                return;
            }
            if (level == res.size()) {
                res.add(new ArrayList<>());
            }
            res.get(level).add(node.val);
            if (node.left != null) {
                bfs2(node.left, level + 1, res);
            }
            if (node.right != null) {
                bfs2(node.right, level + 1, res);
            }
        }

        public void bfs3(TreeNode node, int level, List<List<Integer>> res) {
            if (node == null) {
                return;
            }
            if (level == res.size()) {
                res.add(new ArrayList<>());
            }
            res.get(level).add(node.val);
            if (node.left != null) {
                bfs3(node.left, level + 1, res);
            }
            if (node.right != null) {
                bfs3(node.right, level + 1, res);
            }
        }

        public void bfs4(TreeNode node, int level, List<List<Integer>> res) {
            if (node == null) {
                return;
            }
            if (level == res.size()) {
                res.add(new ArrayList<>());
            }
            res.get(level).add(node.val);
            if (node.left != null) {
                bfs4(node.left, level + 1, res);
            }
            if (node.right != null) {
                bfs4(node.right, level + 1, res);
            }
        }

    }

}
